数据结构(三) 字符串模式匹配KMP和基于哈希的匹配

data-structure 评论

没想到吧，竟然是同一天写的，先安利一个kmp视频，看完之后你看代码就有感觉了。
但是还是感觉哈希流批，万物基于哈希（滑稽）

###链接 B站链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    //用c++的编译器吧，这里我用到了动态内存
    int *next;

    void getNext(char* p)
    {
        int lenp = strlen(p);
        next[0] = -1; //第一个是未知的，就放上-1
        int k = -1;//指针指在字符串最外面
        int j = 0;  //指针指在首地址上
        while (j < lenp - 1)
        {
            //p[k]表示前缀，p[j]表示后缀
            if (k == -1 || p[j] == p[k])
            {
                ++k;
                ++j;
                next[j] = k;
            }
            else
            {
                k = next[k];
            }
        }
    }

    int Kmp(char* s, char* p)
    {
        int i = 0;
        int j = 0;
        int lens = strlen(s);
        int lenp = strlen(p);
        while (i < lens && j < lenp)
        {
            //如果j = -1,或者当前字符匹配成功即 S[i] == P[j]，都令指针移动
            if (j == -1 || s[i] == p[j])
            {
                i++;
                j++;
            }
            else
            {
                //如果j != -1，且当前字符匹配失败，则令 i 指针不懂，j 回退
                j = next[j];   //next[j]即为j所对应的next值
            }
        }
        if (j == lenp)
            return i - j;  //返回下标
        else
            return -1;
    }


    int main()
    {
        char str1[1024]="helloOWorldNotheloWhy??helhellelo";
        char str2[1024]="hellelo";

        next=new int[strlen(str2)+1];//next 数组长度应该比匹配串大一

        getNext(str2);

        printf("%d",Kmp(str1,str2));
        delete[] next;
        return 0;
    }


哈希匹配

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    //基于哈希的模式匹配

    typedef unsigned long long ULL;//用编译器最大的数据类型 2^64

    const ULL HashConst=100000007;//哈希基数 mod hashConst

    int hash_machting(char *a,char *b)//这次是判a是否在b中出现
    {
        int lena=strlen(a);
        int lenb=strlen(b);

        if(lena>lenb) return -1;//a太长了

        ULL t=1;
        //计算哈希计数的lena次方
        for(int i=0;i<lena;++i) t*=HashConst;

        //计算a和b为lena的前缀对应的哈希值
        ULL ah=0,bh=0;
        for(int i=0;i<lena;++i) ah=ah*HashConst+a[i];
        for(int i=0;i<lena;++i) bh=bh*HashConst+b[i];


        //匹配 更新哈希值
        for(int i=0;i+lena<=lenb;i++)
        {
            if(ah==bh) return i;
            if(i+lena<lenb) bh=bh*HashConst+b[i+lena]-b[i]*t;
        }
        return -1;
    }

    int main()
    {
        char str1[1024]="helloOWorldNotheloWhy??helhellelo";
        char str2[1024]="hellelo";

        printf("%d\n",hash_machting(str2,str1));
        return 0;
    }

LTitanC++/Python & Algorithm

个人简介。